package cn.edu.jxau.test;

import java.util.BitSet;
import java.util.Objects;

/**
 * @author Fudashi
 */
public class BloomFilter {

	public static void main(String[] args) {

		BloomFilter filter = new BloomFilter(100, 0.0001);
		filter.add("Hello");
		filter.add("World");
		filter.add("NIhao");
		filter.add("bdfw");
		System.out.println(filter.contains("Hello"));
		System.out.println(filter.contains("World"));
		System.out.println(filter.contains("NIhao"));
		System.out.println(filter.contains("bdfw"));
		System.out.println(filter.contains("adgrh"));
		System.out.println(filter.contains("dhdf"));
		System.out.println(filter.contains("dbqrg"));
		System.out.println(filter.contains("nfgfu"));
		System.out.println(filter.contains("fdgjsd"));
	}

	private final int n;
	private final double p;
	private final int m;
	private final int k;
	private final int[] seedArr; // 质数种子
	private BitSet bitSet;

	/**
	 * 给定数据大小n，误判率p，求位数组大小m，hash函数个数k的公式如下
	 * m = -n * logp/(log2)^2
	 * k = m/n * log2
	 * 
	 * @param n 数据规模
	 * @param p 误判率
	 */
	public BloomFilter(int n, double p) {

		this.n = n;
		this.p = p;
		m = (int) (-n * Math.log(p) / Math.pow(Math.log(2), 2));
		k = (int) (m / n * Math.log(2));
		seedArr = new int[k];
		int i = 0;
		for (int j = 41; true; j++) {
			if (isPrime(j)) {
				seedArr[i++] = j;
				if (i == seedArr.length) {
					break;
				}
			}
		}
		bitSet = new BitSet((int) m);
		System.out.println(n + "\t" + p + "\t" + m + "\t" + k);
	}

	public void add(String value) {

		Objects.requireNonNull(value, "参数value不能为null");
		for (int i = 0; i < k; i++) {
			bitSet.set(index(value, seedArr[i]));
		}
	}

	public boolean contains(String value) {

		for (int i = 0; i < k; i++) {
			if (!bitSet.get(index(value, seedArr[i]))) {
				return false;
			}
		}
		return true;
	}

	private int index(String value, int seed) {
		return hash(value, seed) & m;
	}

	private int hash(String value, int seed) {

		int result = 0;
		int len = value.length();
		for (int i = 0; i < len; i++) {
			result = seed * result + value.charAt(i);
		}
		return result;
	}

	private static boolean isPrime(int num) {

		int end = num >> 1;
		for (int i = 2; i <= end; i++) {
			if (num % i == 0) {
				return false;
			}
		}
		return true;
	}
}